The invention relates generally to the field of printing. More specifically, the invention relates to a method and apparatus for distributing the error resulting from quantizing the pixels of an image.
Image information (whether color or black and white) is commonly derived by scanning in a greyscale format containing a large number of levels (e.g., 256 levels for black and white and more than 16 million levels for color). The resulting image is often unprintable by standard printers. Standard printers print in a limited number of levels. In the binary case, a printer prints at two levels, either a spot or no spot. In a quaternary case, four levels are printed, which may correspond to no spot or one of three different spot sizes. Greyscale image data may be represented in a very large number of values. Accordingly, it is necessary to reduce greyscale image data to the limited number of levels to enable a printer to print the image.
One standard method of converting greyscale pixel image data to binary level pixel image data is through the use of dithering or halftoning processes. In such processes, each greyscale pixel within a given area is compared to one of a set of preselected thresholds comprising a matrix of threshold values (or a halftone cell). The effect of such an arrangement is that for an area where the image is gray, some of the thresholds within the matrix are exceeded, while others are not. In the binary case, the portions of the matrix (or cell elements) in which the thresholds are exceeded are printed as black, while the remaining elements remain white. The effect of the distribution of black and white over the cell is integrated by the human eye as a shade of gray.
Dithering presents problems in that the amount of gray within an original image is not maintained exactly over an area because the finite number of elements inside each halftone cell only allows the reproduction of a finite number of greyscale levels. The error arising from the difference between the threshold value and the actual greyscale value at any particular cell is simply thrown away. This results in loss of image information and the formation of image artifacts. A known example is the banding (or false contour) artifact that can be seen in smooth image areas. The image input greyscale varies smoothly over an image area, while the halftoned image has to make a transition from one halftone dot (greyscale) to another. This transition can clearly be seen as a band running through smooth image parts. Also, these errors create undesirable textures and long range patterns, often referred to as worms.
Algorithms that convert grayscale images to binary or other number of level images attempting to preserve gray density are known. Known error diffusion methods attempt to maintain gray by making the conversion from gray pixels to binary or other level pixels on a pixel-by-pixel basis. The methods compare each pixel to a threshold, and the difference between the greyscale pixel value and the threshold is distributed to a selected group of neighboring pixels in accordance with a weighting method. The adjusted image pixels are then fed back as inputs to the processing method. In this way, the error calculated includes all errors previously distributed.
One example is an error diffusion algorithm, as taught in xe2x80x9cAn Adaptive Algorithm for Spatial Greyscalexe2x80x9d by Floyd and Steinberg, Proceedings of the SID 17/2, 75-77 (1976) (hereinafter, xe2x80x9cFloyd and Steinbergxe2x80x9d). The Floyd and Steinberg method proposes distribution of error determined in the quantization of the nth pixel in scan line l (i.e., pixel position n, l) for the distribution matrix including pixels at pixel locations corresponding to pixels {(n+1, l), (nxe2x88x921, l+1), (n, l+1), (n+1, 1+1)}. Distribution weighting in accordance with the method is given by {(n+1, l)=0.4375, (nxe2x88x921, l+1)=0.1875 (n, l+1)=0.3125 (n+1, l+1)=0.0625}. See FIG. 1 for a block diagram representation of the Floyd and Steinberg error distribution coefficients.
An alternative error diffusion method is taught in xe2x80x9cImages from Computers,xe2x80x9d by M. R. Schroder (sometimes spelled Schroeder) in IEEE Spectrum, pp. 66-78 (1969) (hereinafter Schroder). In this method, the error is only calculated between the original input pixel and the output, neglecting all previously distributed errors. This method leads to a poorer greyscale representation than the Floyd and Steinberg approach, but to higher image contrast. Modifications to the algorithm by Schroder are taught in xe2x80x9cDesign of Optimal Filters for Error-Feedback Quantization of Monochrome Picturesxe2x80x9d by Jung Guk Kim and Gil Kim, Information Sciences 39, pp. 285-298 (1986).
In representing small variations in image appearance with an error diffusion technique, large areas of the image are required for the variation to be represented. Thus, while error diffusion is effective in maintaining gray over the image, it requires a rather large area of the image for the error compensation to be effective. Over such areas, undesirable textures and long-range patterns (e.g., worms), inherent in the distribution of error, may occur. Such artifacts particularly appear in the highlight and shadow areas of an image rendered with the original coefficient set proposed by Floyd and Steinberg.
Other error diffusion methods have been proposed that have more complex and elaborate error diffusion techniques. These other techniques still result in images with worms and can require significant computational resources to implement. These techniques also conserve intensity, resulting in propagating the errors over the entire image, instead of keeping the errors localized. A need exists for a simple error distribution method that keeps the error localized and avoids elements, (e.g., worms) that are caused by phase distortion.
This invention relates to methods and apparatus of diffusing error caused by quantizing each pixel within an image formed of a plurality of pixels. This invention utilizes simple error processing, thus minimizing the computing resources necessary to implement. By implementing a simple error processing with lossy and linear phase characteristics, this invention keeps errors localized and eliminates worms and random noise that degrades a printed image.
In one aspect, the invention relates to a method of diffusing error caused by quantizing each pixel within an image formed of a plurality of pixels, each pixel representing a greyscale value of the image at a location (n, l) within the image, and having an original greyscale value associated therewith. The method includes the steps of adding to the original greyscale value of a pixel having a position (n, l) within the image a first error term resulting from quantization of previously processed pixels to derive a modified greyscale value, comparing the modified greyscale value of the pixel with a threshold to select an output value representing the pixel, calculating a second error term having a value that is the difference between the output value and the modified greyscale value, and distributing the second error term to a preselected plurality of neighboring pixels at positions (n+1, l), (nxe2x88x921, l+1), (n, l+1), (n+1, l+1) using a linear phase filter algorithm having a set of distribution coefficients with a sum less than one, wherein one of the coefficients within the set of coefficients is combined with the second error term for each pixel position. The method also includes these steps being repeated for each pixel within the image. In another embodiment, the linear phase filter algorithm uses finite impulse response techniques. In another embodiment, the combining of one coefficient with the second error term for each pixel position is accomplished by multiplying each coefficient by the second error term. In another embodiment, the portion of the second error term distributed to the pixel at position (n+1, l+1) equals the portion of the second error term distributed to the pixel at position (nxe2x88x921, l+1). In another embodiment, the portion of the second error term distributed to the pixel at position (nxe2x88x921, l+1) combined with the portion of the second error term for the pixel at position (n+1, l+1) equals the portion of the second error term for the pixel at position (n, l+1). In another embodiment, the portion of the second error term distributed to the pixel at position (n+1, l) equals the sum of the portion of the second error term of the pixel at position (n+1, l+1) combined with the portion of the second error term of the pixel at position (n, l+1) and combined with the portion of the second error term of the pixel at position (nxe2x88x921, l+1). In another embodiment, the portion of the second error term distributed to the pixel at position (n+1, l) is about 0.484375, the portion of the second error term distributed to the pixel at position (nxe2x88x921, l+1) is about 0.12109375, the portion of the second error term distributed to the pixel at position (n, l+1) is about 0.2421875 and the portion of the second error term distributed to the pixel at position (n+1, l+1) is about 0.12109375. In another embodiment, the order in which the pixels are processed is determined using raster scanning. In another embodiment, the order in which the pixels are processed is determined using serpentine scanning.
In another aspect, the invention features a method of diffusing error caused by quantizing each pixel within an image formed of a plurality of pixels, each pixel representing a greyscale value of the image at a location within the image, and having an original greyscale value associated therewith. This method includes the steps of adding to the original greyscale value of a pixel having a position (n, l) within the image a first error term resulting from quantization of previously processed pixels to derive a modified greyscale value, comparing the modified greyscale value of the pixel with a threshold to select an output value representing the pixel, calculating a second error term having a value that is less than the difference between the output value and the modified greyscale value, and distributing the second error term to a preselected plurality of neighboring pixels at positions (n+1, l), (nxe2x88x921, l+1), (n, l+1), (n+1, l+1), wherein the portion of the second error term distributed to the pixel at position (n+1, l+1) equals the portion of the second error term distributed to the pixel at position (nxe2x88x921, l+1), and the portion of the second error term distributed to the pixel at position (nxe2x88x921, l+1) combined with the portion of the second error term for the pixel at position (n+1, l+1) equals the portion of the second error term for the pixel at position (n, l+1), and the portion of the second error term distributed to the pixel at position (n+1, l) equals the sum of the portion of the second error term of the pixel at position (n+1, l+1) combined with the portion of the second error term of the pixel at position (n, l+1) and combined with the portion of the second error term of the pixel at position (nxe2x88x921, l+1). These steps are repeated for each pixel within the image. In another embodiment, the order in which the pixels are processed is determined using raster scanning. In another embodiment, the order in which the pixels are processed is determined using serpentine scanning. In another embodiment, the portion of the second error term distributed to the pixel at position (n+1, l) is about 0.484375, the portion of the second error term distributed to the pixel at position (nxe2x88x921, l+1) is about 0.12109375, the portion of the second error term distributed to the pixel at position (n, l+1) is about 0.2421875 and the portion of the second error term distributed to the pixel at position (n+1, l+1) is about 0.12109375.
In another aspect, the invention features an error diffusion system for diffusing error caused by quantizing each pixel within an image formed of a plurality of pixels, each pixel representing a greyscale value of the image at a location (n, l) within the image, and having an original greyscale value associated therewith. The system includes a first summing module for adding to the original greyscale value of a pixel having a position (n, l) within the image a first error term resulting from quantization of previously processed pixels to derive a modified greyscale value, a second summing module operatively connected to the output of the first summing module and the output of the quantizer for calculating a second error term having a value that is less than the difference between the output value and the modified greyscale value, a quantizer operatively connected to the output of the first module comparing the modified greyscale value of the pixel with a threshold to select an output value representing the pixel, and an error filter module operatively connected to the input of the first summing module and the output of the second summing module for distributing the second error term, to preselected plurality of neighboring pixels at positions (n+1, l), (nxe2x88x921, l+1), (n, l+1), (n+1, l+1) using a linear phase filter algorithm having a set of distribution coefficients with a sum less than one, wherein one of the coefficients within the set of coefficients is combined with the second error term for each pixel position. In another embodiment, the linear phase filter algorithm of the error filter module uses finite impulse response techniques. In another embodiment, the combining of one coefficient with the second error term for each pixel position is accomplished by multiplying each coefficient by the second error term. In another embodiment, the error filter module further distributes the second error term such that the pixel at position (n+1, l+1) equals the portion of the second error term distributed to the pixel at position (nxe2x88x921, l+1). In another embodiment, the error filter module further distributes the second error term such that the pixel at position (nxe2x88x921, l+1) combined with the portion of the second error term for the pixel at position (n+1, l+1) equals the portion of the second error term for the pixel at position (n, l+1). In another embodiment, the error filter module further distributes the second error term such that the pixel at position (n+1, l) equals the sum of the portion of the second error term of the pixel at position (n+1, l+1) combined with the portion of the second error term of the pixel at position (n, l+1) and combined with the portion of the second error term of the pixel at position (nxe2x88x921, l+1). In another embodiment, the error filter module further distributes the second error term to preselected plurality of pixels, including pixels at positions (n+1, l), (nxe2x88x921, l+1), (n, l+1), (n+1, l+1), such that the portion of the second error term distributed to the pixel at position (n+1, l) is about 0.484375, the portion of the second error term distributed to the pixel at position (nxe2x88x921, l+1) is about 0.12109375, the portion of the second error term distributed to the pixel at position (n, l+1) is about 0.2421875 and the portion of the second error term distributed to the pixel at position (n+1, l+1) is about 0.12109375. In another embodiment, the order in which the pixels are processed is determined using raster scanning. In another embodiment, the order in which the pixels are processed is determined using serpentine scanning. In another embodiment, the output of the quantizer is operatively connected to a device used to print the image. In another embodiment, the system includes a memory element, including a storage location for at least some of the pixels in the plurality of pixels of an image, wherein the portion of the second error term distributed to a particular pixel is added to contents of the designated storage location of that particular pixel.